package code1_100.code91_100;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 *
 * 执行用时： * 0 ms * , 在所有 Java 提交中击败了 * 100.00% * 的用户
 * 内存消耗： * 36.8 MB * , 在所有 Java 提交中击败了 * 23.05% * 的用户
 *
 * 此方法优于传统递归方法，但空间复杂度还有待优化空间，后续可继续深入。
 *
 */
public class _94treeBianliMiddle {

    // 中序遍历，List为题中要求的输出
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null||stack.size()!=0){
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        for (TreeNode node : stack ) {
            list.add(node.val);
        }
        return list;
    }

    // 重新写一遍中序遍历
    public static void inorderTraversal1(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            System.out.println(root.val);
            root = root.right;
        }
    }

    // 先序便利
    public static List<Integer> oneOrderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode node;
        while (stack.size()!=0){
            node = stack.pop();
            if(node!=null){
                list.add(node.val);
                stack.push(node.right);
                stack.push(node.left);
            }
        }

//        for (TreeNode n : stack ) {
//            list.add(n.val);
//        }
        return list;
    }

    // 触类旁通写出后序便利
    public static List<Integer> lastOrderTraversal(TreeNode root) {
        //list只是题目要求，用于输出
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack.push(root);
        TreeNode node;
        while (stack.size()!=0){
            node = stack.pop();
            //思路来源：先序是跟左右，左右换一下为根右左。整体再用一个栈换一下则为左右跟
            stack2.push(node);
            if (node.left!=null) stack.push(node.left);
            if (node.right!=null) stack.push(node.right);
        }
        while (stack2.size()!=0){
            list.add(stack2.pop().val);
        }
        return list;
    }

    public static void main(String[] args) {
        //先序结果：1245736
        //中序结果：4275136
        //后序结果：4752631
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node5.left = node7;
        node2.left = node4;
        node2.right = node5;
        node3.right = node6;
        root.right = node3;
        root.left = node2;
        for (Integer a:lastOrderTraversal(root)) {
            System.out.print(a+" ");
        }
    }
}
